The present invention relates to cryptographic systems, and more particularly to a method of generating a cipher key based on information difference in a cryptographic system and to a cryptographic system for performing this method.
Cryptographic systems are widely used to ensure the privacy and authenticity of messages transmitted over insecure communication channels such as public telephone lines. They are heavily relied on in military, diplomatic and business communications of information, including voice, picture and text data, and for identification purposes.
One type of cryptographic system, generally known as a privacy cryptosystem, prevents the extraction of information by unauthorized parties from messages transmitted over an insecure communication channel, thus assuring a transmitter that a message being transmitted is read only by an intended receiver.
A conventional type of privacy cryptosystem allows a transmitter to transmit a plaintext message over, for instance, a telephone line to a receiver. At the transmitter's site, an encryption device encodes with a secret key the plaintext message into a ciphertext message which is then transmitted. At the receiver's site, a decryption device decodes the ciphertext message by means of the same secret key back into the plaintext message. Given the secret key, the transformations on the message can be performed, whereas they cannot be performed without knowledge of the secret key, to the present state of mathematical knowledge, even with the most powerful computers known. Thus, for an eavesdropper who wants to decipher the message and yet is assumed to have no information about the secret key, it is infeasible to determine the plaintext message corresponding to a given ciphertext or to determine the secret key even if he were given matching plaintext/ciphertext pairs.
A problem inherent to this conventional type of privacy cryptosystem is that it requires the distribution of secret keys to the communicating parties. This is often done over a secure channel such as priority mail, or in advance by a trusted courier, which has the drawback of being expensive and may even be impossible, as in many military applications.
While in theory it is possible for an eavesdropper to break this conventional type of privacy cryptosystem, for instance by an exhaustive key search, this is completely infeasible if the key is sufficiently long (e.g., a string of 100 random bits). However, none of the presently used privacy cryptosystems is such that the computational security can be proved, i.e. no rigorous proof can be given in any of these cryptosystems that there exists no essentially faster way of breaking the cipher than by an exhaustive key search in which the cryptanalyst tries all possible keys to decipher the given ciphertext until the resulting decrypted ciphertext is one that makes sense, for instance by representing plain English text. When the amount of ciphertext is reasonably large, only one key will produce a valid plaintext message, which then also is the correct plaintext message.
In 1949, Shannon proved that ciphers can be built which are impossible to break, even for an eavesdropper with unrestricted computing power (cf. C. E. Shannon, "Communication theory of secrecy systems", Bell Syst. Tech. J., vol. 28, Oct. 1949, pp. 656-715). Such ciphers are called unconditionally secure. There is a simple explanation of how such unconditional security can be achieved: even if the eavesdropper uses all possible keys to decipher the message, all the resulting plaintexts are valid plaintexts and thus it is impossible for the eavesdropper to choose the correct one among them.
A well-known example of unconditionally secure cipher is the so-called one-time pad originally proposed by Vernam (G. S. Vernam, "Cipher printing telegraph systems for secret wire and radio telegraphic communications", J. Amer. Inst. Elec. Eng., vol. 55, 1926, pp. 109-115). In this kind of cipher, a completely random string of the same length as the plaintext is used as the secret key, and the ciphertext is obtained by adding bit by bit modulo 2 the bit sequences of the plaintext and key strings, addition modulo 2 being defined by the rules 0+0=0; 0+1=1; 1+0=1; 1+1=0. The one-time pad achieves perfect security in the sense that the eavesdropper's optimal strategy for determining the plaintext is provably independent of the ciphertext, in other words, the ciphertext is statistically independent of the plaintext.
A drawback of unconditionally secure ciphers is that the secret key used to encipher a plaintext must be at least as long as the total amount of said plaintext, as has been proved by Shannon. This secret key must be distributed in advance by some secure means, and in most applications it is completely impractical to use such long secret keys.
Shannon's analysis of unconditionally secure ciphers and the proof concerning the minimum amount of secret key required to achieve the described type of unconditional security is based on the assumption that error-free communication channels are used, i.e. that the legitimate receiver as well as the eavesdropper receive an exact copy of the ciphertext message transmitted by the transmitter. However, transmissions over communication channels used in real telecommunications are subject to distortion by noise, i.e., the received signal is not identical to the transmitted signal. By providing sufficient redundancy in the transmitted signal, for instance by transmitting each signal several times or by using error-correcting codes, a channel can be made virtually error-free. More precisely, transmitted messages can be taken from a finite set of possible messages and then, with an arbitrarily small probability of making a wrong decision, the receiver can decide which message was transmitted. Examples of such channels are computer network links. For every channel, the amount of information which can reliably be transmitted in a given time interval is characterized by the capacity of the channel and is finite (see R. G. Gallager, "Information theory and reliable communications", New York: John Wiley, 1968, for a definition of channel capacity). It should be noted that although many communication channels, for instance computer data links, appear to their users to be virtually error-free, the underlying unprotected channel is not error-free.
By way of example, let a channel be considered whose input and output both are binary, i.e. either 0 or 1. Let the error probability of the channel be 10%, i.e. there is a probability of 10% that a transmitted 0 is flipped into a 1 at the receiver, and similarly, there is a probability of 10% that a transmitted 1 is flipped into a 0. A very simple method of increasing the reliability of communications over such a channel is to transmit every bit several times, for instance 7 times. In this instance, after receiving 7 bits, which need not be identical because errors may have occurred on the channel, the receiver will make a majority decision, i.e. the receiver decides that the bit actually transmitted is the bit that is contained 4 or more times in the set of 7 received bits. It can be shown that the bit-error probability is reduced from 10% to 0.43% by means of this very simple error-correcting code.
An error-correcting (n,k) block code is a transformation which assigns to every information word of length k a code word of length n, wherein the information word and code word digits are taken from some finite alphabets. Most often the two alphabets are identical and n&gt;k. When the alphabet is the set {0,1} the code is called a binary code. A very important class of error-correcting codes is comprised of so-called linear codes in which every code word digit is a linear combination of the information word digits. Addition of binary digits is performed modulo 2 as defined above. Thus, the sum of several bits is equal to 1 if and only if the number of ones among the summed terms is odd, else the sum is equal to 0. A particular and important class of linear codes is comprised of so-called systematic codes for which the code word is the information word together with an appended sequence of n-k parity check bits. By way of example, a linear systematic (7,3) code is one which encodes an information word [x.sub.1,x.sub.2, x.sub.3 ] into the code word [x.sub.1,x.sub.2, x.sub.3, x.sub.1 +x.sub.2,x.sub.1 +x.sub.3,x.sub.2 +x.sub.3,x.sub.1 +x.sub.2 + x.sub.3 ], i.e., the parity check bits consist of all combinations of 2 or 3 information word bits. For instance, when the code is binary the code word assigned to the information word 101 is 1011010.
As mentioned above, the information and code word digits can be taken from any finite set of digits, e.g. the set {0,1,2,3,4,5,6}, although the most often used codes are binary. In the general case, the addition operation for adding two elements of the taken set must be defined. Usually, this is the addition operation of a finite mathematical group corresponding to the taken set, and then, a linear combination of digits can be defined as the sum of elements of a subset of the taken set, where every subset corresponds to a different linear combination. It is generally accepted and should be noted that, in this context, the taken set itself also is one of said subsets, i.e. the linear combination of digits may be the sum of some or all elements of the taken set. In the above example of the set {0,1,2,3,4,5,6} the addition operation can be defined as addition modulo 7, so that for instance 1+4=5; 3+6=2; 5+3+4+6=4; etc., and a linear combination of digits is an addition modulo 7 thereof.
Many communication channels, in particular satellite and radio communication channels, have the property that not only a legitimate receiver but also any other receiver within a certain range can receive the transmitted signal. However, the noise which corrupts the received signals is different for every receiver. The thermal noise within a receiver is statistically independent of that of the other receivers, and the noise introduced by the actual transmission (e.g. the atmospheric noise) is, to a certain degree, also independent for different receivers. The received signal power and- thus the quality of the received signal depends on the location of the receiver with respect to the transmitter and decreases with the square of the distance of the receiver to the transmitter.
A communication channel with one transmitter but possibly several receivers each having a different respective noise is called a broadcast channel. When a system is designed to allow error-free communication between the transmitter and a legitimate receiver, then also another receiver can receive the transmitted information reliably, as long as its signal-to-noise power ratio is at least equal to that of the legitimate receiver. On the other hand, when the eavesdropper's noise is stronger he may not be able to make a reliable decision about the transmitted message even when the legitimate receiver can. Thus, when in a cryptographic communication system the eavesdropper's channel is worse than the legitimate receiver's channel, then it is possible to transmit information securely regardless of the eavesdropper's computing power and manpower. This fact was first pointed out by Wyner (see A. D. Wyner, "The wire-tap channel", Bell Syst. Tech. J., vol. 54, Oct. 1975, no. 8, pp. 1355- 1387). The intuitively obvious fact that such secure communication is possible if and only if the eavesdropper's channel is worse was proved by Csiszar and Korner (see I. Csiszar and J. Korner, "Broadcast channels with confidential messages", IEEE Trans. on Info. The., vol. IT-24, no. 3, May 1978, pp. 339-348).
However, in most cryptographic scenarios it is unrealistic and very dangerous to assume that the eavesdropper's channel is worse than the legitimate receiver's channel. For instance, it is dangerous to assume that the eavesdropper's receiving antenna is smaller than the legitimate receiver's antenna. However, it may be reasonable to assume that the ratio of the eavesdropper's antenna to the legitimate receiver's antenna is not greater than some number, e.g. 10 or 100.